pub mod prelude {
    use std::{
        fmt::Display,
        ops::{Add, Div, Mul, Neg, Sub},
    };

    pub trait NativeNumber:
        Display
        + Default
        + Clone
        + Copy
        + Add<Output = Self>
        + Mul<Output = Self>
        + Neg<Output = Self>
        + Sub<Output = Self>
        + Div<Output = Self>
        + From<i8>
    {
    }

    impl NativeNumber for isize {}
    impl NativeNumber for i8 {}
    impl NativeNumber for i16 {}
    impl NativeNumber for i32 {}
    impl NativeNumber for i64 {}
    impl NativeNumber for i128 {}
    impl NativeNumber for f32 {}
    impl NativeNumber for f64 {}

    #[derive(Debug, Default, Clone, PartialEq, Eq)]
    pub struct Matrix<T: NativeNumber>(Vec<T>, (usize, usize));

    impl<T: NativeNumber> Matrix<T> {
        pub fn new() -> Self {
            Self(Vec::new(), (0, 0))
        }
        pub fn from(data: &[T], row: usize, col: usize) -> Self {
            Self(Vec::from(data), (row, col))
        }
        pub fn from_fn(func: fn(usize, usize) -> T, row: usize, col: usize) -> Self {
            let mut r = 0;
            let mut c = 0;
            let data = (0..row * col)
                .map(|_| {
                    let elem = func(r, c);
                    c += 1;
                    if c == col {
                        c = 0;
                        r += 1;
                    }
                    elem
                })
                .collect();
            Self(data, (row, col))
        }
        pub fn from_rows(rows: &[Vec<T>]) -> Self {
            let data = rows.iter().flatten().copied().collect::<Vec<_>>();
            Self(data, (rows[0].len(), rows.len()))
        }
        pub fn from_cols(cols: &[Vec<T>]) -> Self {
            Self::from_rows(cols).trans()
        }
        pub fn get_row(&self, row: usize) -> &[T] {
            let (_, col) = self.get_shape();
            &self.get_data()[(row * col)..(row * col + col)]
        }
        pub fn get_rows(&self) -> Vec<Vec<T>> {
            let (_, col) = self.get_shape();
            self.get_data()
                .chunks(col)
                .map(|row| row.to_vec())
                .collect()
        }
        pub fn get_col(&self, col: usize) -> &[T] {
            let (row, _) = self.get_shape();
            &self.trans().0.leak()[(col * row)..(row * col + row)]
        }
        pub fn get_cols(&self) -> Vec<Vec<T>> {
            self.trans().get_rows()
        }
        pub fn swap_row(&mut self, r1: usize, r2: usize) {
            let mut data = self.get_rows();
            data.swap(r1, r2);
            self.0 = data.into_iter().flatten().collect::<Vec<_>>();
        }
        pub fn swap_col(&mut self, r1: usize, r2: usize) {
            let mut data = self.get_cols();
            data.swap(r1, r2);
            self.0 = data.into_iter().flatten().collect::<Vec<_>>();
        }
        pub fn eyes(row: usize, col: usize) -> Self {
            let rank = if row > col { col } else { row };
            let mut data = vec![Default::default(); row * col];
            for i in 0..rank {
                data[i * col + i] = T::from(1i8);
            }
            Self(data, (row, col))
        }
        pub fn zeros(row: usize, col: usize) -> Self {
            Self(vec![Default::default(); row * col], (row, col))
        }
        pub fn get_shape(&self) -> (usize, usize) {
            self.1
        }
        pub fn get_data(&self) -> &[T] {
            &self.0
        }
        pub fn set_elem(&mut self, elem: T, row: usize, col: usize) {
            let (_, c) = self.get_shape();
            self.0[row * c + col] = elem;
        }
        pub fn map(&self, func: fn(T) -> T) -> Self {
            let data = self.get_data().iter().map(|elem| func(*elem)).collect();
            let (row, col) = self.get_shape();
            Self(data, (row, col))
        }
        pub fn inv(&self) -> Self {
            self.adjoint().reduce(self.det())
        }
        pub fn adjoint(&self) -> Self {
            let (row, col) = self.get_shape();
            let mut data = Vec::new();
            for c in 0..col {
                for r in 0..row {
                    data.push(self.minor(r, c));
                }
            }
            Self::from(&data, row, col)
        }
        pub fn trans(&self) -> Self {
            let (row, col) = self.get_shape();
            let mut data = Vec::new();
            for c in 0..col {
                for r in 0..row {
                    data.push(self.get_data()[r * col + c]);
                }
            }
            Self::from(&data, col, row)
        }
        pub fn det(&self) -> T {
            let (row, col) = self.get_shape();
            let data = self.get_data();
            if row == 2 {
                data[0] * data[3] - data[1] * data[2]
            } else if row == 1 {
                data[0]
            } else {
                let mut ans = Default::default();
                for i in 0..row {
                    ans = ans + self.minor(i, 0) * data[i * col];
                }
                ans
            }
        }
        pub fn scale(&self, num: T) -> Self {
            let (row, col) = self.get_shape();
            let data = self.get_data();
            Self::from(
                &data.iter().map(|elem| num * *elem).collect::<Vec<_>>(),
                row,
                col,
            )
        }
        pub fn reduce(&self, num: T) -> Self {
            let (row, col) = self.get_shape();
            let data = self.get_data();
            Self::from(
                &data.iter().map(|elem| *elem / num).collect::<Vec<_>>(),
                row,
                col,
            )
        }
        pub fn minor(&self, i: usize, j: usize) -> T {
            let (row, col) = self.get_shape();
            let mut data = Vec::new();
            for r in (0..i).chain((i + 1)..row) {
                for c in (0..j).chain((j + 1)..col) {
                    data.push(self.get_data()[r * col + c]);
                }
            }
            let algo_minor = Self::from(&data, row - 1, col - 1).det();
            if (i + j) & 1 == 1 {
                algo_minor.neg()
            } else {
                algo_minor
            }
        }
    }

    impl<T: NativeNumber> Add for &Matrix<T> {
        type Output = Matrix<T>;
        fn add(self, rhs: Self) -> Self::Output {
            let (row, col) = self.get_shape();
            Matrix::from(
                &self
                    .get_data()
                    .iter()
                    .zip(rhs.get_data().iter())
                    .map(|(x, y)| *x + *y)
                    .collect::<Vec<T>>(),
                row,
                col,
            )
        }
    }

    impl<T: NativeNumber> Sub for &Matrix<T> {
        type Output = Matrix<T>;
        fn sub(self, rhs: Self) -> Self::Output {
            let (row, col) = self.get_shape();
            Matrix::from(
                &self
                    .get_data()
                    .iter()
                    .zip(rhs.get_data().iter())
                    .map(|(x, y)| *x - *y)
                    .collect::<Vec<T>>(),
                row,
                col,
            )
        }
    }
    impl<T: NativeNumber> Mul<T> for &Matrix<T> {
        type Output = Matrix<T>;
        fn mul(self, rhs: T) -> Self::Output {
            let mut data = Vec::new();
            let (row, col) = self.get_shape();
            for r in 0..row {
                for c in 0..col {
                    let elem = rhs * self.get_data()[r * col + c];
                    data.push(elem);
                }
            }
            Matrix::from(&data, row, col)
        }
    }

    impl<T: NativeNumber> Mul for &Matrix<T> {
        type Output = Matrix<T>;
        fn mul(self, rhs: Self) -> Self::Output {
            let self_data = self.get_data();
            let rhs_data = rhs.get_data();

            let (lrow, lcol) = self.get_shape();
            let (rrow, rcol) = rhs.get_shape();
            let lcol = if rrow < lcol { rrow } else { lcol };

            let mut data = Vec::new();
            for r in 0..lrow {
                for c in 0..rcol {
                    let mut elem: T = Default::default();
                    for m in 0..lcol {
                        elem = elem + self_data[r * lcol + m] * rhs_data[m * rcol + c];
                    }
                    data.push(elem);
                }
            }
            Matrix::from(&data, lrow, rcol)
        }
    }

    impl<T: NativeNumber> Display for Matrix<T> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            let data = self.get_data();
            let (row, col) = self.get_shape();
            let mut s = String::new();
            for r in 0..row {
                for c in 0..col {
                    s += &format!("{:.4} ", data[r * col + c]);
                }
                s += "\n";
            }
            write!(f, "{}", s)
        }
    }
} /* prelude */

#[cfg(test)]
mod tests {
    use std::ops::Mul;

    use crate::prelude::Matrix;

    #[test]
    fn times() {
        let a = Matrix::from(&[1, 2, 3, 4], 2, 2);
        let b = Matrix::from(&[2, 5, 6, 8], 2, 2);
        let c = &a * &b;
        let d = &c * 2;
        assert_eq!(a, Matrix::from(&[1, 2, 3, 4], 2, 2));
        assert_eq!(b, Matrix::from(&[2, 5, 6, 8], 2, 2));
        assert_eq!(c, Matrix::from(&[14, 21, 30, 47], 2, 2));
        assert_eq!(d, Matrix::from(&[28, 42, 60, 94], 2, 2));
    }
}
